|
In computer science, BNF (Backus Normal Form or Backus–Naur Form) is one of the two main notation techniques for context-free grammars, often used to describe the syntax of languages used in computing, such as computer programming languages, document formats, instruction sets and communication protocols; the other main technique for writing context-free grammars is the van Wijngaarden form. They are applied wherever exact descriptions of languages are needed: for instance, in official language specifications, in manuals, and in textbooks on programming language theory. Many extensions and variants of the original Backus–Naur notation are used; some are exactly defined, including ''Extended Backus–Naur Form'' (EBNF) and ''Augmented Backus–Naur Form'' (ABNF). ==History== The idea of describing the structure of language using rewriting rules can be traced back to at least the work of Pāṇini (who lived sometime between the 7th and 4th century BC).〔(【引用サイトリンク】title=Panini biography )〕〔 Ingerman suggests that the Backus Normal Form be renamed to the Pāṇini-Backus Form, to give due credit to Pāṇini as the earliest independent inventor.〕 His notation to describe Sanskrit word structure notation is equivalent in power to that of Backus and has many similar properties. In Western society, grammar was long regarded as a subject for teaching, rather than scientific study; descriptions were informal and targeted at practical usage. In the first half of the 20th century, linguists such as Leonard Bloomfield and Zellig Harris started attempts to formalize the description of language, including phrase structure. Meanwhile, string rewriting rules as formal, abstract systems were introduced and studied by mathematicians such as Axel Thue (in 1914), Emil Post (1920s–40s) and Alan Turing (1936). Noam Chomsky, teaching linguistics to students of information theory at MIT, combined linguistics and mathematics, by taking what is essentially Thue's formalism as the basis for the description of the syntax of natural language. He also introduced a clear distinction between generative rules (those of context-free grammars) and transformation rules (1956). John Backus, a programming language designer at IBM, proposed a metalanguage of "metalinguistic formulas"〔The meaning of syntactic formula may be further explained by saying that words enclosed in the brackets < >, like 〕〔 〕〔 〕 to describe the syntax of the new programming language IAL, known today as ALGOL 58 (1959), and first used in the ALGOL 60 report. BNF is a notation for Chomsky's context-free grammars. Apparently, Backus was familiar with Chomsky's work.〔 〕 As proposed by Backus, the formula defined "classes" whose names are enclosed in angle brackets. For example, Further development of ALGOL led to ALGOL 60. In the committee's 1963 report, Peter Naur called Backus's notation Backus Normal Form. Donald Knuth argued that BNF should rather be read as Backus–Naur Form, as it is "not a normal form in the conventional sense",〔 〕 unlike, for instance, Chomsky Normal Form. The name Pāṇini Backus form has also been suggested in view of the fact that the expansion Backus Normal Form may not be accurate, and that Pāṇini had independently developed a similar notation earlier. 〔 〕 BNF, as described by Peter Naur in the ALGOL 60 report are ''metalinguistic formula''. "''Sequences of characters enclosed in the brackets <> represent metalinguistic variables whose values are sequences of symbols. The marks "::=" and "|" (the latter with the meaning of "or") are metalingustic connectives. Any mark in a formula, which is not a variable or a connective, denotes itself. Juxtaposition of marks and/or variables in a formula signifies juxtaposition of the sequence denoted.''" 〔Revised ALGOL 60 report section. 1.1.(【引用サイトリンク】title=ALGOL 60 )〕 Another example from the ALGOL 60 report illustrates a major difference of the BNF metalanguage and a Chomsky context sensitive grammar. Metalingustic variables do not require a rule defining their formation. Their formation may simply be described in natural language within the <> brackets. The following ALGOL 60 report section 2.3 comments specification, exemplifies how this works: For the purpose of including text among the symbols of a program the following "comment" conventions hold: By equivalence is here meant that any of the three structures shown in the left hand column may be replaced, in any occurrence outside of strings, by the symbol shown in the same line in the right hand column without any effect on the action of the program. (end ALGOL quote) Naur changed two of Backus's symbols to commonly available characters. The "::=" symbol was originally a ":≡". The "|" symbol was originally the word "" (with a bar over it).〔 Working for IBM, Backus would have had a non-disclosure agreement and couldn't have talked about his source if it came from an IBM proprietary project. BNF is very similar to canonical form boolean algebra equations that are, and were at the time, used in logic circuit design. Backus was a mathematician and the designer of the FORTRAN programming language. Studies of boolean algebra is commonly part of a mathematics. What we do know is that neither Backus nor Naur described the names enclosed in < > as non-terminals. Chomsky terminology was not originally used in describing BNF. Naur later described them as classes in ALGOL course materials.〔 In the ALGOL 60 report they were called metalinguistic variables. Anything other than the meta symbols ::=, |, and class names in closed in <,> are symbols of the language being defined. The meta symbols ::= is to be interpreted as "is defined as". The | is used to separate alternative definitions and is interpreted as "or". The meta symbols <,> are delimiters enclosing a class name. BNF is described as a metalanguage for talking about ALGOL by Peter Naur and Saul Rosen.〔 In 1947 Saul Rosen became involved in the activities of the fledgling Association for Computing Machinery, first on the languages committee that became the IAL group and eventually led to ALGOL. He was the first managing editor of the Communications of the ACM. What we do know is that BNF was first used as a metalanguage to talk about the ALGOL language in the ALGOL 60 report. That is how it is explained in ALGOL programming course material developed by Peter Naur in 1962.〔 Early ALGOL manuals by IBM, Honeywell, Burroughs and Digital Equipment Corporation followed the ALGOL 60 report using it as a metalanguage. Saul Rosen in his book describes BNF as a metalanguage for talking about ALGOL. An example of its use as a metalanguage would be in defining an arithmetic expression: : The first symbol of an alternative may be the class being defined. As explained by Naur; The meaning of which is to specify a sequence beginning with a previous alternative.〔 For example, above In some later metalanguages such Schorre's META II the BNF recursive repeat construct is replaced by a sequence operator and target language symbols defined using quoted strings. The < and > bracket removed. Mathematical grouping ( ) were added. The :EXPR = TERM $("+" TERM .out "ADD" | "-" TERM .out "SUB"); These changes made META II and its derivative programming languages that are able to define and extend their own metalanguage. In so doing the ability to use a natural language description, meta linguistic variable, language construct description was lost. Many spin-off metalanguages were inspired by BNF. See META II, TREE-META, and Metacompiler. A BNF class describes a language construct formation, with formation defined as a pattern or the action of forming the pattern. The class name expr is described in a natural language as a : There are no specifics on white space in the above. As far as the rule states we could have space between the digits. In the natural language we complement the BNF metalanguage by explaining that the digit sequence can have no white space between the digits. English is only one of the possible natural languages. Translations of the ALGOL reports were available in many natural languages. The origin of BNF is not as important as its impact on programming language development. During the period immediately following the publication of the ALGOL 60 report BNF was the basis of many compiler-compiler systems. Some directly used BNF like "A Syntax Directed Compiler for ALGOL 60" developed by E. T. Irons and "A Compiler Building System" Developed by Brooker and Morris. Others changed it to a programming language. The Schorre Metacompilers made it a programming language with only a few changes.. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Backus–Naur Form」の詳細全文を読む スポンサード リンク
|